/*!
 * # [53.最大子数组和](https://leetcode.cn/problems/maximum-subarray/description/)
 *
 * @lc app=leetcode.cn id=53 lang=rust
 *
 * ## 难度 
 * - Medium (54.86%)
 * - Likes:    5842
 * - Dislikes: 0
 * - Total Accepted:    1.3M
 * - Total Submissions: 2.4M
 * - Testcase Example:  '[-2,1,-3,4,-1,2,1,-5,4]'
 *
 * ## 问题描述
 *
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分。
 *
 * ## 示例 1：
 * - 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * - 输出：6
 * - 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 *
 * ## 示例 2：
 * - 输入：nums = [1]
 * - 输出：1
 *
 * ## 示例 3：
 * - 输入：nums = [5,4,-1,7,8]
 * - 输出：23
 *
 * ## 提示：
 * - 1 <= nums.length <= 10^5
 * - -10^4 <= nums[i] <= 10^4
 *
 * ## 进阶：
 *
 * 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
 *
 */

use super::*;

// @lc code=start
impl Solution {
    /// # 最大子数组和
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设 dp[i]: 以nums[i]为尾的最大连续子数组和;
    /// 2. 则 dp[i] = max(dp[i-1]+nums[i], nums[i])
    /// 3. 初始条件: dp[0] = nums[0]
    /// 4. 目标值: max(dp[i])
    pub fn max_sub_array1(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        assert!(n > 0);
        let mut dp = vec![0; n];
        dp[0] = nums[0];
        let mut res = dp[0];
        for i in 1..n {
            dp[i] = nums[i].max(dp[i - 1] + nums[i]);
            res = res.max(dp[i]);
        }

        res
    }

    /// - 优化: dp[i]只和dp[i-1]相关, 可用两个整形变量代替;
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        assert!(n > 0);
        let mut dp = nums[0];
        let mut res = dp;
        for i in 1..n {
            dp = nums[i].max(dp + nums[i]);
            res = res.max(dp);
        }

        res
    }
}
// @lc code=end
//
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test() {
        // assert_eq!(Solution::max_sub_array(vec![]), 0);
        assert_eq!(Solution::max_sub_array(vec![-2,1,-3,4,-1,2,1,-5,4]), 6);
        assert_eq!(Solution::max_sub_array(vec![1]), 1);
        assert_eq!(Solution::max_sub_array(vec![5,4,-1,7,8]), 23);
    }
}
